#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/17 8:57
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _79_exits.py
from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        rows = len(board)
        cols = len(board[0])

        visited = [[False for _ in range(cols)] for _ in range(rows)]

        def dfs(row:int, col:int, index:int)->bool:

            if board[row][col] != word[index]:
                return False
            elif index == len(word) - 1:
                return True


            visited[row][col] = True
            for d in dirs:
                next_row = row + d[0]
                next_col = col + d[1]
                if 0<=next_row<rows and 0<=next_col<cols and not visited[next_row][next_col]:
                    if dfs(next_row, next_col, index + 1):
                        return True
            visited[row][col] = False
            return False

        for row in range(rows):
            for col in range(cols):
                if board[row][col]==word[0]:
                    if dfs(row, col, 0):
                        return True
        return False

if __name__ == '__main__':
    a = Solution().exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE")
    print(a)